package graph.matchProblem;
/**
 * 
 * @Title: CandyHungarian.java 
 * @Package graph.matchProblem 
 * @Description: 匈牙利算法求解匹配问题
 * @author CandyWall   
 * @date 2021年1月23日 下午5:07:33 
 * @version V1.0
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

import graph.unweighted.CandyGraph;
import graph.unweighted.dfs.biPartitionDetection.CandyBiPartitionDetection;

public class CandyHungarian {
    private CandyGraph graph;
    private int maxMatching;
    private int[] matching;
    
    public CandyHungarian(CandyGraph graph) {
        if(graph.isDirected()) {
            throw new IllegalArgumentException("二分图匹配问题只能处理无权图！");
        }
        CandyBiPartitionDetection biPartitionDetection = new CandyBiPartitionDetection(graph);
        if(!biPartitionDetection.isBiPartitionGraph()) {
            throw new IllegalArgumentException("当前图不是二分图！");
        }
        this.graph = graph;
        matching = new int[graph.getVertex_num()];
        Arrays.fill(matching, -1);
        
        ArrayList<Integer>[] biParts = biPartitionDetection.getBiParts();
        for(int v : biParts[0]) {
            if(matching[v] == -1) {
                // 寻找增广路径
                if(bfs(v))
                    maxMatching++;
            }
        }
    }
    
    /**
     * 寻找增广路径
     * @param v
     * @return 
     */
    private boolean bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        int[] pres = new int[graph.getVertex_num()];
        Arrays.fill(pres, -1);
        queue.add(v);
        pres[v] = v;
        
        while(!queue.isEmpty()) {
            int cur = queue.remove();
            for(int next : graph.adjacentVertexes(cur)) {
                if(pres[next] == -1) {
                    if(matching[next] != -1) {
                        
                    }
                    pres[next] = cur;
                    queue.add(next);
                }
            }
        }
        return true;
    }

    /**
     * 获取最大匹配数
     * @return
     */
    public int getMaxMatching() {
        return maxMatching;
    }
    
    /**
     * 获取完美匹配数
     * @return
     */
    public boolean isPerfectMatching() {
        return maxMatching * 2 == graph.getVertex_num();
    }

    public static void main(String[] args) {
        CandyGraph graph1 = new CandyGraph("testData/matchProblem/graph1.txt");
        CandyHungarian candyHungarian1 = new CandyHungarian(graph1);
        System.out.println("最大匹配数：" + candyHungarian1.getMaxMatching() + "，是否是完美匹配：" + candyHungarian1.isPerfectMatching());
        CandyGraph graph2 = new CandyGraph("testData/matchProblem/graph2.txt");
        CandyHungarian candyHungarian2 = new CandyHungarian(graph2);
        System.out.println("最大匹配数：" + candyHungarian2.getMaxMatching() + "，是否是完美匹配：" + candyHungarian2.isPerfectMatching());
        CandyGraph graph3 = new CandyGraph("testData/matchProblem/graph3.txt");
        CandyHungarian candyHungarian3 = new CandyHungarian(graph3);
        System.out.println("最大匹配数：" + candyHungarian3.getMaxMatching() + "，是否是完美匹配：" + candyHungarian3.isPerfectMatching());
        CandyGraph graph4 = new CandyGraph("testData/matchProblem/graph4.txt");
        CandyHungarian candyHungarian4 = new CandyHungarian(graph4);
        System.out.println("最大匹配数：" + candyHungarian4.getMaxMatching() + "，是否是完美匹配：" + candyHungarian4.isPerfectMatching());
    }
}
